GLPKで楽しく最適化しよう！

since 2004/05/01　last update 2005/04/08　access:
new! 最新版 glpk4.8 をアップロードしました。
new! 久しぶりに記事を追加しました。
new! GLPKスーパー簡易マニュアルを追加しました。

このページの目的

GLPK(GNU Linear Programming Kit)は最適化の入門者からプロまで幅広く使える
大変良くできたフリーの線形計画ソルバーです。
しかし残念なことに日本においてはほとんど普及しておらず、
付属マニュアルも英語のため、とても敷居の高いものになっています。
また、Unix上で動かすことが前提で作られているので、Windows上で
動作させることがなかなか面倒です。
そこで、WindowsのDOSで動作するようにバイナリも配布することにしました。

このページでは数理計画とは何か、から初めて
実際にGLPKを動かしてもらい、簡単な例題を通してGLPKによるモデリングを
理解できるように構成しています。
そのため、プロの方には多少冗長に感じられるかもしれませんが
ご容赦ください。
日本における最適化分野の発展に少しでも貢献することができれば
大変幸いであります。

Contents

0. GLPKのインストール

1. GLPK(Gnu Linear Programming Kit)とは？
2. GLPKのインストール
3. GLPKスーパー簡易マニュアル

1. 線形計画法(LP)

1. 数理計画(Mathematical Programming)とは？
2. 簡単な例(線形計画法 : LP)
3. よりよいモデリングへ
   1. まえおき
   2. モデルファイル・データファイルとは？
   3. モデルファイル
   4. データファイル
4. おわりに

2. 整数計画法(IP)

1. 整数計画法(Integer Programming)とは？
2. 例題:おつりのコイン数を最小にしよう
   1. 問題
   2. 欲張り法(greedy method)
   3. GLPKを用いた定式化
3. 例題:クマさんを盗んで儲けよう？
   1. 0-1整数計画とは？
   2. 問題
   3. 欲張り法によるアイディア
   4. GLPKを用いた定式化
4. おわりに

3. LP,IPの応用

1. バランスの良いチームを作ろう
   1. 問題
   2. この問題の特徴
   3. 方策1: 総合力のばらつきをなくそう
   4. 方策2:特徴のばらつきをなくそう
2. 実験データを集計しよう
   1. 問題
   2. 通常のアプローチ
   3. 偏差最小の定式化
   4. 絶対値を外す
   5. GLPKによるモデル
3. 続・実験データを集計しよう
   1. 最小自乗法をLPで実現する
   2. 凸関数・凹関数
   3. 区分線形近似
   4. 多重選択型定式化
   5. 凸結合定式化
4. なるべく安く運ぶには？
   1. 問題
   2. ネットワークの表現
   3. フロー整合条件
   4. 定式化
   5. GLPKによるモデル
   6. 完全単模と整数性
5. 続・なるべく安く運ぶには？
   1. 固定費用付き輸送問題
   2. 実数と整数の対応
   3. グラフで見てみよう
   4. 定式化
   5. GLPKによるモデル